//
// Description: 1137. 第 N 个泰波那契数
// Created by Loading on 2021/8/8.
//

#include <bits/stdc++.h>

using namespace std;

int tribonacci(int n) {
    /* 舍弃递归，会超时 */
    if (n == 0) {
        return 0;
    }
    if (n == 1 || n == 2) {
        return 1;
    }
    int n1 = 0, n2 = 1, n3 = 1;
    int res = 0;
    for (int i = 3; i <= n; ++i) {
        res = n1 + n2 + n3;
        n1 = n2;
        n2 = n3;
        n3 = res;
    }

    return res;
}

int main() {
    int n = 37;
    int res = tribonacci(n);
    cout << res << endl;
}